#include <stdio.h>
#include <time.h>
#include <stdlib.h>

struct sort_time_{
	char *sort_name;
	unsigned int time_us;
	unsigned int time_ms;
	unsigned int time_s;
	struct sort_time_ *prve;
	struct sort_time_ *next;
};
static struct sort_time_ *sort_time_head = NULL;

struct optctx_{
	int quantity;
	int digit;
};
static struct optctx_ optctx;

char get_opt(int index, char *argv[], char **value)
{
	*value = argv[index+1];

	if ( *argv[index] != '-' ||  *value == NULL || **value == '-')
	{
		return 'h';
	}
	return *(argv[index]+1);
}
void show_help()
{
	printf("Usage:	sort_test [options] [value]\n\
	-h	show help\n\
	-n number	number of sorts (10 <= number <= 10000000 )\n\
	-d digit	max of digit (1 <= digit <= 7)\n");
	
	return;
}
int parse_options(struct optctx_ *optctx, int argc, char *argv[])
{
	int i = 0;
	char * value = NULL;
	int valid = 0;
	if (argc < 3)
	{
		show_help();
		return -1;
	}
	for (i = 1; i < argc - 1; i += 2)
	{
		switch ( get_opt(i, argv, &value) )
		{
			case 'h':
				show_help();
				return -1;	
			case 'n':
				optctx->quantity = atoi(value);
				break;
			case 'd':
				optctx->digit = atoi(value);
				break;
			default:
				show_help();
				printf("unknow opt: %s  \n",argv[i]);
				return -1;
		}
	}
        if (optctx->quantity < 10 || optctx->quantity > 100000000)
	{
		show_help();
		printf("number quantity %d is invalid\n");
		return -1;
	}
	if (optctx->digit < 1 || optctx->digit > 7)
	{
		show_help();
		printf("digit %d is invalid\n");
		return -1;
	}
	return 0;
}




int range(int digit)
{
	int range = 1;
	int i = 0;
	for (i = 0;i < digit; i++)
	{
		range *= 10;
	}
	return range;
}


void data_fill(int *data, int data_lenth, int digit)
{
	int i;
	for (i = 0; i<data_lenth; i++)
	{
		data[i] = rand()%range(digit);
	}
	return 0;
}
void printf_data(int *data, int data_lenth)
{
	int i,j;
	int column = 10;
	
	printf("data[%d]:",data_lenth);
	for (i = 0, j = 0; i<data_lenth; i++, j++)
	{
		if ( (j % 10) == 0)
		{
			printf("\n");
		}
		printf("%d\t", data[i]);
	}
	printf("\n");
}

static inline unsigned int getcurtime()
{
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return (unsigned int) (tv.tv_sec * 1000000 + tv.tv_usec );
}

void printf_sort_time()
{
	struct sort_time_ *p = sort_time_head->next;
	while(p != NULL)
	{
		printf("%-20s\t%ds:\t%dms:\t\t%dus\n",p->sort_name, p->time_s, p->time_ms, p->time_us);
		p = p->next;	
	}
	return;
}
void add_sort_time_node(unsigned int stime, unsigned int etime, char *sort_name, int data_lenth)
{
	unsigned int time_us = etime - stime;
	unsigned int time_ms = time_us/1000;
	unsigned int time_s = time_ms/1000;
	

	struct sort_time_ *new = malloc(sizeof(struct sort_time_));
	new->sort_name = sort_name;
	new->time_us = time_us;
	new->time_ms = time_ms;
	new->time_s = time_s;
	new->next = NULL;
	new->prve = NULL;


	if (sort_time_head == NULL)
	{
		sort_time_head = malloc(sizeof(struct sort_time_));
		sort_time_head->next = new;
		new->prve = sort_time_head;
	}
	else
	{
		struct sort_time_ *p = sort_time_head->next;
		while (p->next && p->time_us < new->time_us)
		{
			p = p->next;
		}
		if (p->next == NULL && p->time_us < new->time_us)
		{
			p->next = new;
			new->prve = p;
		}
		else
		{
			p->prve->next = new;
			new->next = p;
			new->prve = p->prve;
			p->prve = new;
		}
	}
/*
	if (time_s != 0)
		printf("%s [%d] : time = %d%s\n",sort_name, data_lenth, time_s, "s");
	else if (time_ms != 0)
		printf("%s [%d] : time = %d%s\n",sort_name, data_lenth, time_ms, "ms");
	else 
		printf("%s [%d] : time = %d%s\n",sort_name, data_lenth, time_us, "us");
*/

}
int check_sort(int *data_sorted, int *data_checked, int data_lenth, char *sort_name)
{
	int i = 0;
	for (i = 0; i < data_lenth; i++)
	{
		if (data_sorted[i] != data_checked[i])
		{
			printf("\033[1;31merror:%s is fail \033[0m \n",sort_name);
			return -1;
		}
	}
	return 0;
}


int main(int argc, char* argv[])
{
	if (parse_options(&optctx, argc, argv))
	{
		return -1;
	}

	int data_lenth = optctx.quantity;
	int bit_range = optctx.digit;
	int *data = malloc(sizeof(int) * data_lenth);
	int *data_tmp = malloc(sizeof(int) * data_lenth);
	int *data_sorted = malloc(sizeof(int)*data_lenth);

	unsigned int stime = 0;
	unsigned int etime = 0;

	srand((int)time(0));

	data_fill(data, data_lenth, bit_range);
	//printf_data(data, data_lenth);

	/*
	 * 冒泡排序测试
	 * */
#if 0
	memcpy(data_tmp, data, data_lenth*4);
	stime = getcurtime();
	bubble_sort(data_tmp, data_lenth);
	etime = getcurtime();
	//printf_data(data_tmp, data_lenth);
	memcpy(data_sorted, data_tmp, data_lenth*4);
	add_sort_time_node(stime, etime, "bubble_sort", data_lenth);
#endif

	/*
	 * 快速排序测试
	 * */
	memcpy(data_tmp, data, data_lenth*4);
	stime = getcurtime();
	quick_sort(data_tmp, data_lenth);
	etime = getcurtime();
	//printf_data(data_tmp, data_lenth);
	memcpy(data_sorted, data_tmp, data_lenth*4);
	//check_sort(data_sorted, data_tmp, data_lenth, "quick_sort");
	add_sort_time_node(stime, etime, "quick_sort", data_lenth);

	/*
	 * 插值排序测试
	 * */
#if 0
	memcpy(data_tmp, data, data_lenth*4);
	stime = getcurtime();
	interpolation_sort(data_tmp, data_lenth);
	etime = getcurtime();
	//printf_data(data_tmp, data_lenth);
	check_sort(data_sorted, data_tmp, data_lenth, "interpolation_sort");
	add_sort_time_node(stime, etime, "interpolation_sort", data_lenth);
#endif

	/*
	 * 希尔排序测试
	 * */
	memcpy(data_tmp, data, data_lenth*4);
	stime = getcurtime();
	shell_sort(data_tmp, data_lenth);
	etime = getcurtime();
//	printf_data(data_tmp, data_lenth);
	check_sort(data_sorted, data_tmp, data_lenth, "shell_sort");
	add_sort_time_node(stime, etime, "shell_sort", data_lenth);

	/*
	 * 选择排序
	 * */
#if 0
	memcpy(data_tmp, data, data_lenth*4);
	stime = getcurtime();
	selection_sort(data_tmp, data_lenth);
	etime = getcurtime();
//	printf_data(data_tmp, data_lenth);
	check_sort(data_sorted, data_tmp, data_lenth, "selection_sort");
	add_sort_time_node(stime, etime, "selection_sort", data_lenth);
#endif
	/*
	 * 堆排序
	 * */
	memcpy(data_tmp, data, data_lenth*4);
	stime = getcurtime();
	heap_sort(data_tmp, data_lenth);
	etime = getcurtime();
//	printf_data(data_tmp, data_lenth);
	check_sort(data_sorted, data_tmp, data_lenth, "heap_sort");
	add_sort_time_node(stime, etime, "heap_sort", data_lenth);

	/*
	 * 归并排序
	 * */
	memcpy(data_tmp, data, data_lenth*4);
	stime = getcurtime();
	merge_sort(data_tmp, data_lenth);
	etime = getcurtime();
	//printf_data(data_tmp, data_lenth);
	check_sort(data_sorted, data_tmp, data_lenth, "merge_sort");
	add_sort_time_node(stime, etime, "merge_sort", data_lenth);

	/*
	 * 基数排序
	 * */
	memcpy(data_tmp, data, data_lenth*4);
	stime = getcurtime();
	radix_sort(data_tmp, data_lenth);
	etime = getcurtime();
	//printf_data(data_tmp, data_lenth);
	check_sort(data_sorted, data_tmp, data_lenth, "radix_sort");
	add_sort_time_node(stime, etime, "radix_sort", data_lenth);


	/*
	 * 基数排序
	 * */
	memcpy(data_tmp, data, data_lenth*4);
	stime = getcurtime();
	radix_linklist_sort(data_tmp, data_lenth);
	etime = getcurtime();
	//printf_data(data_tmp, data_lenth);
	check_sort(data_sorted, data_tmp, data_lenth, "radix_linklist_sort2");
	add_sort_time_node(stime, etime, "radix_linklist_sort2", data_lenth);


	printf_sort_time();


	free(data);
	free(data_tmp);
	free(data_sorted);
	return 0;
}
